public class code01 {
    // 力扣 150 在排序数组中查找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        // 使用两次二分查找
        // 分别的，第一次查找负责寻找左边界，第二次查找负责寻找右边界

        // 首先定义两个指针，分别指向左右两个边界
        int left = 0;
        int right = nums.length - 1;

        // 定义两个值，用来记录开始和结束
        int first = -1;
        int last = -1;

        // 进行第一次二分查找，尝试找到左边界上的值
        while(left <= right) {
            // 找到中间值
            int mid = (left + right) / 2;
            // 尝试寻找合适的值
            if(nums[mid] == target) {
                // 记录左侧下标
                first = mid;
                // --- 重点 ---
                // 因为要找的是 左边界 ，所以这里直接将右边界向前移动一位
                right = mid - 1;
            } else if(nums[mid] > target) {
                // 更新右边界
                right = mid - 1;
            } else {
                // 更新左边界
                left = mid + 1;
            }
        }

        // 在进行第二次二分查找之前，需要先将当前的两个指针恢复到原位
        left = 0;
        right = nums.length - 1;

        // 进行第二次二分查找
        while(left <= right) {
            // 同样找到中间值
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                // 此时找到了 目标值
                last = mid;
                // --- 重点 ---
                // 将左指针直降向中间点后移动一位，因为要找的是右边界
                left = mid + 1;
            } else if(nums[mid] < target) {
                // 更新左边界
                left = mid + 1;
            } else {
                // 更新右边界
                right = mid - 1;
            }
        }

        // 按照要求定义一个返回值
        return new int []{first,last};
    }
}
